import java.util.Arrays;

/**
 * @Author: wanqian
 * @Date: 2021/2/2 16:18
 */
public class QuickSortHole {
    public static int[] arr = {42, 12, 50, 99, 50, 34, 21, 50, 66};
    private static int count = 0;


    public static void main(String[] args) {
        int[] arr = new int[1000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 1000);
        }
//        System.out.println(String.format("快速排序前： %s", Arrays.toString(arr)));
        long start = System.currentTimeMillis();
        quickSort(arr, 0, arr.length - 1);
        long end = System.currentTimeMillis();
        long consume = (end - start);
        System.out.println("耗时" + consume + "毫秒");
//        System.out.println(String.format("快速排序后： %s", Arrays.toString(arr)));
    }


    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int l = left;
            int r = right;
            //保存pivot值（挖坑）
            int pivot = arr[l];
            //终止while循环以后left和right一定相等的
            while (l < r) {
                //从右向左找到小于pivot的数
                while (l < r && arr[r] >= pivot) {
                    r--;
                }
                //将小于pivot的数放到之前挖的坑(arr[left])中
                //arr[right]成为一个新坑
                arr[l] = arr[r];

                //从左向右找到大于pivot的数
                while (l < r && arr[l] <= pivot) {
                    l++;
                }
                //将大于pivot的数放到之前挖的坑(arr[right])中
                //arr[left]成为一个新坑
                arr[r] = arr[l];
            }
            // 此时l=r, 就是中轴线
            // 左侧的数都<=pivot, 右侧的数>=pivot
            arr[l] = pivot;
//            System.out.println(String.format("排序：%s", Arrays.toString(arr)));
            quickSort(arr, l + 1, right);
            quickSort(arr, left, r - 1);
        }
    }
}
